#include "element.h" 
#include "arbre.h" 
#include <assert.h>
#include <stdio.h>
#include <stdlib.h> 



/* ------------------------------ */
/* Declaration Fonctions internes */
/* ------------------------------ */

static void initialiserNoeud(Noeud *pN, Elem e); 
/* Precondition : *pN non prealablement initialise, e prealablement initialise 
   Postcondition : le noeud initialise est un noeud feuille contenant dans son 
   champ info une copie de e */


static void detruireAPartirDe(Noeud *pN, Arbre *pA);
/* Precondition : *pA initialise, pN est l'adresse d'un noeud valide de l'arbre *pA, 
   ou NULL. 
   Postcondition : Libere la mémoire pour tous les noeuds du sous-arbre issu de *pN,
   pN inclus. Attention, le pointeur donné en paramètre ne doit plus être
   utilise après appel à cette procédure (pour faire plus propre, on aurait pu utiliser
   un pointeur de pointeur **ppN, afin de pouvoir mettre *ppN à NULL,
   et eviter une erreur de l'utilisateur). */


static void insererElementDansSSArbre(Elem e, Noeud ** ppN, Arbre *pA);
/* Preconditions : 
   1) *pA est un arbre binaire de recherche initialisé et non vide;
   2) ppN est l'adresse d'une case memoire contenant une adresse de noeud 
      de l'arbre *pA (adresse du champ adRacine de l'arbre, ou adresse du 
      champ fg ou fd d'un noeud de l'arbre *pA);    
   3) l'insertion du mot dans le sous-arbre enracine en **ppN ne viole pas la 
      propriete d'arbre binaire de recherche de *pA
   Postcondition : si e n'existait pas deja dans l'arbre *pA, alors
   un nouveau noeud contenant e est insere aux feuilles de *pA. Si au contraire 
   e existait deja dans l'arbre, alors l'arbre reste inchange. */



/* ----------- */
/* Definitions */
/* ----------- */


/* ---------------------- */
/* Vie et mort des arbres */
/* ---------------------- */

static void initialiserNoeud(Noeud *pN, Elem e)
{
  pN->info = e;
  pN->fg = NULL;
  pN->fd = NULL;
}


void initialiserArbre(Arbre *pA)
{
 	pA->adRacine=NULL;
	pA->nbElemDansArbre=0;
}


void testamentArbre(Arbre *pA)
{
	if(pA->adRacine != NULL)
	{
		detruireAPartirDe(pA->adRacine,pA);
		pA->nbElemDansArbre=0;
		pA->adRacine=NULL;
	}
}

static void detruireAPartirDe(Noeud *pN, Arbre *pA)
{
  if(pN != NULL)
  {
  	detruireAPartirDe(pN->fg,pA);
  	detruireAPartirDe(pN->fd,pA);
  	free(pN);
  }
}



void insererElement(Elem e, Arbre *pA) 
{
	insererElementDansSSArbre(e, &(pA->adRacine), pA);
}

static void insererElementDansSSArbre(Elem e, Noeud ** ppN, Arbre *pA)
{
	if( *ppN == NULL)
	{
		*ppN=(Noeud*)malloc(sizeof(Noeud));
		initialiserNoeud(*ppN, e);
		pA->nbElemDansArbre=pA->nbElemDansArbre+1;
	}
	else
	{
			if (!estIdentique(e,(*ppN)->info))
			{
				if (estInferieurEnY(e,(*ppN)->info))
				{
					insererElementDansSSArbre(e,&((*ppN)->fg),pA);
				}
				if (estSuperieurOuEgalEnY(e,(*ppN)->info))
				{
					insererElementDansSSArbre(e,&((*ppN)->fd),pA);
				}
			}
	}	 
}

int testArbreVide(Arbre A)
{
  if (A.adRacine==NULL) return 1;
  else return 0;
}

/*
void suppression(Noeud * pere,Noeud * pN)
{
	if(pN->fg== NULL && pN-> fd == NULL)
	{
		
	} 
	if(pN->fg == NULL && pN->fd != NULL)
	{
		pere->fg=pN->fd;
	}
	if(pN->fd == NULL && pN->fg != NULL)
	{
		pere->fd=pN->fg;
	}
	if()
	{
		
	}
}*/
void suppressionRacine(Arbre *pA,Noeud * pN)
{
	if(pN->fg== NULL && pN-> fd == NULL)
	{
		pA->adRacine=NULL;
		free(pN);
	}
	if(pN->fg == NULL && pN->fd != NULL)
	{
		pA->adRacine=pN->fd;
	}
	if(pN->fd == NULL && pN->fg != NULL)
	{
		pA->adRacine=pN->fg;
	}

}
void supprimerNoeuds(Elem e,Arbre * pA,Noeud *pere, Noeud *pN, int * trouve)
{
	
	if(pN != NULL)
	{	/* cas racine == element */
		if(pere == pN && estIdentique(pN->info, e))
		{
			*trouve=1;
			suppressionRacine(pA,pN);
		}
	}/*
		else
		{
			pere=pN;
			if(estIdentique(pN->info, e))
			{
				*trouve=1;
				suppression(pere,pN);
			}
			if(estInferieurEnY(e, pN->info))
			{
				supprimerNoeuds(e,pere,pN->fg,trouve);
			}
			if(estSuperieurEnY(e,pN->info))
			{
				supprimerNoeuds(e,pere,pN->fd,trouve);
			}
		}
	}*/
}

void supprimerElement(Elem e, Arbre * pA, int * trouve)
{
  supprimerNoeuds(e, pA,pA->adRacine,pA->adRacine,trouve);
  if(*trouve == 1)
  {
  pA->nbElemDansArbre=pA->nbElemDansArbre-1;
  }
}

/* ----------- */
/*  Affichage  */
/* ----------- */

void affichageNoeuds(Noeud *pN)
{
  if (pN != NULL)
    {
      affichageNoeuds(pN->fg);
      afficherElem(pN->info);  
      printf("\n");
      affichageNoeuds(pN->fd);
    }
}

void affichageArbre(Arbre A)
{ 
	printf("le nombre d'élements dans l'arbre est : %d\n",A.nbElemDansArbre);
  affichageNoeuds(A.adRacine);
}

